This invention relates generally to digital electronic circuits and more particularly to a method and apparatus for producing a weighted average of two numbers.
Digital electronic circuits experience increasing requirements for efficiency such as faster operating speed and smaller area requirements. One digital circuit that commonly faces such requirements is a linear interpolator. A linear interpolator is a digital circuit that produces the weighted average of two terms. The weight of the two terms are represented as a percentage, always between 0 and 1. Furthermore, the sum of the two weights is always equal to 1 (100%):
Referring to FIG. 1, a conventional linear interpolator 10 includes two multipliers 12, 14, a carry-save addition ("CSA") tree 16 and an adder 18. To produce a weighted average Z of two term T1 and T2, where the term T1 has a weight of frac1 and the term T2 has a weight of frac2, the following equations apply: ##EQU1##
The conventional linear interpolator 10 has several problems associated with it, concerning both speed and area. The (1-frac2) weight must always be resolved before the multiplication can precede, such resolution being in the critical speed path in the linear interpolator. The speed of the linear interpolator 10 is directly dependent on the number of consecutive "levels" of logical operations, such as additions or subtractions. Therefore, the extra level of addition required by the (1-frac2) operation not only requires extra circuitry, but hinders the speed of the linear interpolator 10.
Furthermore, each multiplier 12, 14 creates a series of partial products which is then reduced to a sum and carry term S1, C1 and S2, C2, respectively. The four terms S1, C1, S2, C2 are further reduced and accumulated by the CSA tree 16 before a final propagation add is performed by the adder 18 to produce the result Z of the linear interpolation. Typically, reduction and accumulation operations reduce groups of three terms into groups of two terms. Although several groups of three terms may be reduced in parallel for each level, the resulting groups of two terms must then be recombined into groups of three which are reduced again.
For example, consider that both the term T1 and the weight frac1 are six bit numbers and a full adder can accommodate three bits. The multiplication process for T1.multidot.frac1 produces six partial products: aaaaaa, bbbbbb, cccccc, dddddd, eeeeee, fffff, before it produces the sum S1 (nnnnnnnnnn) and carry C1 (ooooooo): ##EQU2##
Therefore, for a linear interpolator with 6-bit fractal weights (frac1, frac2), there are 6 partial products which require three levels of full addition in each multiplier 12, 14. In addition, since the results from the multipliers 12, 14 (terms C1, S1, C2 and S2) are being provided to the CSA tree 16, an extra two levels of addition for the CSA tree are also required to reduce the four terms to two (terms A1, A2). Also, the adder 18 requires an additional level of addition before producing the weighted average Z along with the level of addition required for the (1-frac2) operation. As a result, many levels of addition are required, which affects adversely the speed of the linear interpolator 10. Furthermore, with an increase in the number of partial products, the number of addition levels increases logarithmically.